<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2183：Pku3137 Enjoyable Commutation</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Pku3137 Enjoyable Commutation</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Pku3137 Enjoyable Commutation</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Pku3137 Enjoyable Commutation                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：259MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">Isaac is tired of his daily trip to his office, using the same shortest route everyday. Although this saves his time, he must see the same scenery again and again. He cannot stand such a boring commutation any more. One day, he decided to improve the situation. He would change his route everyday at least slightly. His new scheme is as follows. On the first day, he uses the shortest route. On the second day, he uses the second shortest route, namely the shortest except one used on the first day. In general, on the k-th day, the k-th shortest route is chosen. Visiting the same place twice on a route should be avoided, of course. You are invited to help Isaac, by writing a program which finds his route on the k-th day. The problem is easily modeled using terms in the graph theory. Your program should find the k-th shortest path in the given directed graph. </span></p>
<p><span style="font-size: medium"><strong><span style="color: red"><em>n</em></span><span style="color: red">结点有向简单图中的简单</span><i><span style="color: red">k</span></i><span style="color: red">短路（结点不能重复经过）</span><span style="color: red">.</span><span style="color: red">路径长度相同时按照字典序排列</span><span style="color: red">.<i>n</i>&lt;=50, <i>k</i>&lt;=200, </span></strong></span></p></p><hr/><h3>输入格式</h3><p><p>The input consists of multiple datasets, each in the following format. n m k a b x1 y1 d1 x2 y2 d2 &hellip; xm ym dm Every input item in a dataset is a non-negative integer. Two or more input items in a line are separated by a space. n is the number of nodes in the graph. You can assume the inequality 2 &le; n &le; 50. m is the number of (directed) edges. a is the start node, and b is the goal node. They are between 1 and n, inclusive. You are required to find the k-th shortest path from a to b. You can assume 1 &le; k &le; 200 and a &ne; b. The i-th edge is from the node xi to yi with the length di (1 &le; i &le; m). Both xi and yi are between 1 and n, inclusive. di is between 1 and 10000, inclusive. You can directly go from xi to yi, but not from yi to xi unless an edge from yi to xi is explicitly given. The edge connecting the same pair of nodes is unique, if any, that is, if i &ne; j, it is never the case that xi equals xj and yi equals yj. Edges are not connecting a node to itself, that is, xi never equals yi. Thus the inequality 0 &le; m &le; n(n &minus; 1) holds. Note that the given graph may be quite unrealistic as a road network. Both the cases m = 0 and m = n(n &minus; 1) are included in the judges&rsquo; data. The last dataset is followed by a line containing five zeros (separated by a space).</p></p><hr/><h3>输出格式</h3><p><p>For each dataset in the input, one line should be output as specified below. An output line should not contain extra characters such as spaces. If the number of distinct paths from a to b is less than k, the string None should be printed. Note that the first letter of None is in uppercase, while the other letters are in lowercase. If the number of distinct paths from a to b is k or more, the node numbers visited in the k-th shortest path should be printed in the visited order, separated by a hyphen (minus sign). Note that a must be the first, and i must be the last in the printed line. In this problem the term shorter (thus shortest also) has a special meaning. A path P is defined to be shorter than Q, if and only if one of the following conditions holds. The length of P is less than the length of Q. The length of a path is defined to be the sum of lengths of edges on the path. The length of P is equal to the length of Q, and P&rsquo;s sequence of node numbers comes earlier than Q&rsquo;s in the dictionary order. Let&rsquo;s specify the latter condition more precisely. Denote P&rsquo;s sequence of node numbers by p1, p2, &hellip;, ps, and Q&rsquo;s by q1, q2, &hellip;, qt. p1 = q1 = a and ps = qt = b should be observed. The sequence P comes earlier than Q in the dictionary order, if for some r (1 &le; r &le; s and r &le; t), p1 = q1, &hellip;, pr &minus; 1 = qr &minus; 1, and pr &lt; qr (pr is numerically smaller than qr). A path visiting the same node twice or more is not allowed.</p></p><hr/><h3>样例输入</h3><pre>5 20 10 1 5
1 2 1
1 3 2
1 4 1
1 5 3
2 1 1
2 3 1
2 4 2
2 5 2
3 1 1
3 2 2
3 4 1
3 5 1
4 1 1
4 2 1
4 3 1
4 5 2
5 1 1
5 2 1
5 3 1
5 4 1
4 6 1 1 4
2 4 2
1 3 2
1 2 1
1 4 3
2 3 1
3 4 1
3 3 5 1 3
1 2 1
2 3 1
1 3 1
0 0 0 0 0
</pre><hr/><h3>样例输出</h3><pre>1-2-4-3-5
1-2-3-4
None


Hint

In the case of the first dataset, there are 16 paths from the node 1 to 5. They are ordered as follows (The number in parentheses is the length of the path).

1 (3) 1-2-3-5 9 (5) 1-2-3-4-5 
2 (3) 1-2-5 10 (5) 1-2-4-3-5 
3 (3) 1-3-5 11 (5) 1-2-4-5 
4 (3) 1-4-3-5 12 (5) 1-3-4-5 
5 (3) 1-4-5 13 (6) 1-3-2-5 
6 (3) 1-5 14 (6) 1-3-4-2-5 
7 (4) 1-4-2-3-5 15 (6) 1-4-3-2-5 
8 (4) 1-4-2-5 16 (8) 1-3-2-4-5 
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Japan 2006 K短路</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2183" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2183" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>